package main

import (
	"container/heap"
)

type intHeap []int

type SeatManager struct {
	seats intHeap
}

func Constructor(n int) SeatManager {
	seats := intHeap{}
	for i := 1; i <= n; i++ {
		seats = append(seats, i)
	}

	heap.Init(&seats)
	return SeatManager{seats}
}

func (this *SeatManager) Reserve() int {
	return heap.Pop(&this.seats).(int)
}

func (this *SeatManager) Unreserve(seatNumber int) {
	heap.Push(&this.seats, seatNumber)
}

func (h intHeap) Len() int {
	return len(h)
}

func (h intHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

func (h intHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *intHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *intHeap) Pop() interface{} {
	res := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return res
}
